from McTree import *

#s = 'abaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaababa'
s = 'MERASCLLLLLLPLVHVSATTPEPCELDDEDFRCVCNFSEPQPDWSEAFQCVSAVEVEIHAGGLNLEPFLKRVDADADPRQYADTVKALRVRRLTVGAAQVPAQLLVGALRVLAYSRLKELTLEDLKITGTMPPLPLEATGLALSSLRLRNVSWATGRSWLAELQQWLKPGLKVLSIAQAHSPAFSYEQVRAFPALTSLDLSDNPGLGERGLMAALCPHKFPAIQNLALRNTGMETPTGVCAALAAAGVQPHSLDLSHNSLRATVNPSAPRCMWSSALNSLNLSFAGLEQVPKGLPAKLRVLDLSCNRLNRAPQPDELPEVDNLTLDGNPFLVPGTALPHEGSMNSGVVPACARSTLSVGVSGTLVLLQGARGFA'
tree = McTree(s)

DFS = [None for i in xrange(0, len(s)+1)]
LL = list(DFS)
i = 0

def traverse(node):
	global DFS
	global LL
	global i
	if isinstance(node, Leaf):
		DFS[node.pos] = i
		LL[i] = node.pos
		i += 1
	else:
		node.DFSstart = i
		for v in node.edges.itervalues():
			traverse(v)
		node.DFSstop = i

traverse(tree.root)

branching = list()
nonbranching = list()

def basicTraverse(node):
	global tree
	global branching
	global DFS, LL
	#iterate over the children
	if isinstance(node, InnerNode):
		if node.strDepth > 0:
			children = [LL[i] for i in xrange(node.DFSstart, node.DFSstop)]
			m = max(children)
			for i in children:
				j = i + node.strDepth
				if node.DFSstart <= DFS[j] and DFS[j] < node.DFSstop:
					if not tree.s[i] == tree.s[i + 2*node.strDepth]:
						branching.append((i, node.strDepth, 2, 0))
		for c in node.edges.itervalues():
			basicTraverse(c)
	

basicTraverse(tree.root)
#rotate
for (i, l, k, b) in branching:
	if i > 0 and tree.s[i-1] == tree.s[i-1+2*l]:
		branching.append((i-1, l, k, 1))

def tandemsort(x,y):
	res = cmp(x[0],y[0])
	if res == 0:
		res = cmp(x[1],y[1])
	return res

branching.sort(tandemsort)

br = 0
non = 0
for (i, l, k, b) in branching:
	print '(%i, %i, %i)' %(i, l, k),
	if b == 0:
		print 'branching'
		br += 1
	else:
		print 'non-branching'
		non += 1
print br, non
